import java.util.ArrayList;
import java.util.Arrays;
import java.util.Locale;

/**
 * Created by L.jp
 * Description:输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
 * 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
 * User: 86189
 * Date: 2022-08-17
 * Time: 17:36
 */
public class Solution {
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> ret=new ArrayList<>();
        char[] strs=str.toCharArray();
        //字典序排序
        Arrays.sort(strs);
        //标记数组，判断是否被访问过
        boolean[] isVisited=new boolean[strs.length];
        //临时的结果
        StringBuilder tmp=new StringBuilder();
        backTrack(strs,tmp,ret,isVisited);
        return ret;
    }
    
    private void backTrack(char[] strs, StringBuilder tmp, ArrayList<String> ret, boolean[] isVisited) {
        if(tmp.length()==strs.length){
            ret.add(tmp.toString());
            return;
        }
        //全排列
        for(int i=0;i< strs.length;i++){
            //去重和去除已经遍历过的
            if(isVisited[i] || i>0 && strs[i]==strs[i-1] && !isVisited[i-1]){
                continue;
            }
            tmp.append(strs[i]);
            //标记为遍历过
            isVisited[i]=true;
            backTrack(strs, tmp, ret, isVisited);
            tmp.deleteCharAt(tmp.length()-1);
            isVisited[i]=false;
        }
    }
}
